﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    private static TreeNode pNode, qNode;
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root is null || root == p || root == q) return root;
        if (p is null) return q;
        if (q is null) return p;
        
        while (root is not null)
        {
            if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >= q.val)) return root;

            if (root.val > p.val && root.val > q.val) root = root.left;
            
            if (root.val < p.val && root.val < q.val) root = root.right;
        }

        return null;
    }

    public static void Main(string[] args)
    {
        int?[] root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5];
        int p = 2, q = 8;

        TreeNode rootNode = CreatBinaryTree(root, p, q);

        Solution solution = new Solution();
        TreeNode node = solution.LowestCommonAncestor(rootNode, pNode, qNode);
        Console.WriteLine(node.val);
    }

    private static TreeNode CreatBinaryTree(int?[] root, int p, int q)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (root is null || root.Length == 0 || root[0] is null) return null;
        
        // 根节点进队
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        TreeNode node;
        int i = 1;
        bool flag;
        while (queue.Count > 0)
        {
            flag = true;
            // 出队
            node = queue.Dequeue();
            
            // 判断时候为qNode,pNode
            if (node.val == p) pNode = node;
            if (node.val == q) qNode = node;
            if (root[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }
            
            if (++i >= root.Length) break;
            if (root[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            if (++i >= root.Length) break;
            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }
}